package com.zry.demo;

public class DeleteLastN {
    private static class Node {
        String data;
        Node next;
    }

    public static void main(String[] args) {
        Node node1 = new Node();
        node1.data = "汪1";

        Node node2 = new Node();
        node2.data = "汪2";

        Node node3 = new Node();
        node3.data = "汪3";

        Node node4 = new Node();
        node4.data = "汪4";

        Node node5 = new Node();
        node5.data = "汪5";

        Node node6 = new Node();
        node6.data = "汪6";

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = null;

        printNode(node1);
        int deleteLastN = 1;

        Node newNode = new DeleteLastN().deleteLastN(node1, deleteLastN);

        printNode(newNode);
    }

    private static void printNode(Node first){
        while (first != null) {
            System.out.print( first.data + ",");
            first = first.next;
        }
        System.out.println();
    }

    /**
     * 假设长度为L,删除倒数n， 相当于正数的 L - (n - 1) 即 L - n + 1
     * 首先我们将添加一个哑结点作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。在第一次遍历中，我们找出列表的长度 LL。然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第 (L - n)(L−n) 个结点那里。我们把第 (L - n)(L−n) 个结点的 next 指针重新链接至第 (L - n + 2)(L−n+2) 个结点，完成这个算法。
     * @param head
     * @param i
     * @return
     */
    private Node deleteLastN(Node head, int i) {
        Node fakeHead = new Node();
        fakeHead.next = head;

        int length = 0;
        Node first = head;
        while (first != null) {
            length++;
            first = first.next;
        }

        length -= i;

        first = fakeHead;

        while (length > 0) {
            length--;
            first = first.next;
        }

        first.next = first.next.next;
        return fakeHead.next;
    }
}
